package codetop.microsoft.T109;

import util.ListNode;
import util.TreeNode;

/**
 * @Author: 18362
 * @Create: 2022-09-07 17:53:26 星期三
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null)
            return null;
        if (head.next == null)
            return new TreeNode(head.val);
        if (head.next.next == null)
            return new TreeNode(head.next.val, new TreeNode(head.val), null);
        ListNode pre = getMidPre(head);
        ListNode mid = pre.next;
        TreeNode right = sortedListToBST(mid.next);
        pre.next = null;
        TreeNode left = sortedListToBST(head);
        return new TreeNode(mid.val, left, right);
    }

    private ListNode getMidPre(ListNode head) {
        ListNode slow = head, fast = head.next, pre = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        return pre;
    }
}